題目連結(https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

今天來談需要思考的應用題型，一維 DP(Dynamic Programming) 動態規劃經典題

1. Repeat（題目重複確認）

• 輸入：一個整數陣列 prices ，prices[i] 表示第 i 天的買價
• 輸出：最大利潤
• 前提：賣的日期不能早於買的日期，如果無法獲利則返回 0

2. Examples（舉例確認理解）

第二天為買價最低，接下來的賣價第五天最高，因此最大利潤為第五天減第二天的價值＝6-1＝5。

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.

特殊案例
Input: prices = [7,6,4,3,1]
Output: 0
Explanation:
- 價格持續下降
- 無法獲利，返回 0

3. Approach（解題思路）

**方法 ：**一維 DP

• 用一個變數 minb 保存 目前最小買價
• 遍歷每一天的價格 prices[i]：
  1. 將 prices[i] 視為賣價，計算利潤 prices[i] - minb
  2. 更新最大利潤 maxp = max(maxp, prices[i] - minb)
  3. 更新最小買價 minb = min(minb, prices[i])
• 時間複雜度：O(n)
• 空間複雜度：O(1)

4. Code（C++）

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int maxp = 0; //初始化最大利潤
        int minb = prices[0]; //初始化最小買價
        for(int i = 0; i < prices.size(); i++){
            int sell = prices[i];
            maxp = max(maxp, sell - minb); //確認利潤會不會比原先儲存的高
            minb = min(minb, sell); //更新最小買價
        }
        return maxp;
    }
};

5. Test 範例

prices = [7,6,4,3,1]
-> maxProfit = 0

prices = [1,2,3,4,5]
-> maxProfit = 4

6. 相關題目與延伸概念

• Best Time to Buy and Sell Stock II (122)：可多次買賣
• Best Time to Buy and Sell Stock III (123)：最多買賣兩次
• Best Time to Buy and Sell Stock IV (188)：最多買賣 k 次
• 一維 DP 範例：透過記錄歷史最小值或最大值即可求解
• Sliding Window 思路：最小值作為左邊界，右邊界遍歷賣價

7. 補充：語法＆注意事項

• 動態規劃：問題可表達成多個子問題重疊(overlap)，並以 bottom-up 方式求解
• maxProfit = dp[i]：到第 i 天為止最大利潤
• minBuy = dp 的狀態：歷史最小買價
• O(n) 遍歷即可完成一維 DP，無需額外陣列

ps. 部分內容經 AI 協助整理